/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
 package kono.utils
{
	//堆，基于数组， Heap, built on a array
	public class Heap
	{
		private var _heap:Array;
		private var _top:uint;
		private var capacity:uint;
		private var compare:Function;
		
		public function Heap(size:uint, compareTo:Function = null)
		{
			_heap = new Array(capacity = size);
			_top = 0;
			if(compareTo == null)
			{
				compare = function (a:Number, b:Number):int
				{
					return int(a-b);
				}
			}
			else
			{
				compare = compareTo;
			}
		}
		
		//得到堆的大小， get the heap's capacity
		public function get size():uint
		{
			return capacity;
		}
		
		//堆首， the first data in the heap
		public function peek():*
		{
			return _heap[0];
		}
		
		//添加新数据到堆， add a new data to heap
		public function push(data:*):void
		{
			_heap[_top] = data;
			var parents:uint = (_top - 1) >> 1;
			while(_top > 0 && parents >= 0)
			{
				if(compare(_heap[_top], _heap[parents]) > 0)
				{
					var temp:* = _heap[parents];
					_heap[parents] = _heap[_top];
					_heap[_top] = temp;
					if(parents > 0)			
						parents = (parents - 1) >> 1;
				}
				else
					break;
			} 
			_top ++;
		}
		
		//删除堆首元素， remove the first data in the heap
		public function pop():void
		{			
			if(_top > 0)
			{
				_heap[0] = _heap[_top -1];			
				var cursor:uint = 0;
				var childs:uint = (_top << 1) + 1;
				childs = _heap[childs] > _heap[childs + 1] ? childs : childs + 1;
				while(childs < _top)
				{					
					if(compare(_heap[cursor], _heap[childs]) < 0)
					{
						var temp:* = _heap[cursor];
						_heap[cursor] = _heap[childs];
						_heap[childs] = temp;
						cursor = childs;
					}
					else
						break;
				} 
				_top--;
			}
			delete 	_heap[_top];
		}
		
		//打印堆结构， print the frame of the heap
		public function print():void
		{
			var space:String = " ";
			for(var i:uint = 0; i < _heap.length; i++)
			{
				space += " ";
				trace(space + _heap[i]);
			}
		}
		
		//清空堆， remove all the data of the heap
		public function clear():void
		{
			_heap = new Array(capacity);
			_top = 0;
		}
		
		//判断给定数据是否包含在堆中， check if the given target exit in the heap
		public function contains(target:*):Boolean
		{
			for(var i:uint = 0; i < _heap.length; i++)
			{
				if(_heap[i] == target)
				{
					return true;
				}
			}
			return false;
		}
		
		//转换堆到数组， convert the heap to a array
		public function toArray():Array
		{
			return _heap;
		}
		
		//返回堆的信息， return a string respreaenting the current heap
		public function toString():String
		{
			return "[Heap, size=" + capacity + "]";
		}
	}
}